package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

import java.util.LinkedList;

/**
 * 力扣第 297 题「二叉树的序列化与反序列化」
 */
public class Codec {
    // 代表分隔符的字符
    String SEP = ",";
    // 代表空指针的字符
    String NULL = "#";

    // 把一棵二叉树序列化成字符串
    public String serialize(TreeNode root) {
        StringBuilder sb  = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }
    private void serialize(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        serialize(root.left,sb);
        serialize(root.right,sb);
    }

    // 把字符串反序列化成二叉树
    public TreeNode deserialize(String data) {
        //将字符串转化为列表
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)) {
            nodes.addLast(s);
        }
        return deserialize(nodes);
    }

    private TreeNode deserialize(LinkedList<String> nodes){
        String first = nodes.removeFirst();
        if (NULL.equals(first)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}
